package one.three.web.three;

public class Queue<Item> {
	private Node first;
	private Node last;
	private int N;

	private class Node {
		Item item;
		Node next;
		Node pre;
	}

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		return N;
	}

	public Item remove(int i) {
		if (i <= N && i >= 1) {

			Node c = first;
			int idx = 1;
			while (idx < i) {
				c = c.next;
				idx++;
			}
			Item r = c.item;
			if (c.pre != null) {
				c.pre.next = c.next;
			}
			if (c.next != null) {
				c.next.pre = c.pre;
			}
			N--;
			return r;
		} else {
			return null;
		}
	}

	public void enqueue(Item item) {
		Node oldFast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		last.pre = oldFast;
		if (isEmpty())
			first = last;
		else
			oldFast.next = last;
		N++;
	}

	public Item dequeue() {
		if (N > 0) {
			Item item = first.item;
			first = first.next;
			if (first != null)
				first.pre = null;
			if (isEmpty())
				last = null;
			N--;
			return item;
		} else {
			return null;
		}
	}

	public static void main(String[] args) {
		Queue<String> q = new Queue<String>();
		q.enqueue("a");
		q.enqueue("b");
		q.enqueue("c");
		q.enqueue("d");

		q.remove(2);

		System.out.println(q.dequeue());
		System.out.println(q.dequeue());
		System.out.println(q.dequeue());
		System.out.println(q.dequeue());
	}

}
